package math;

public class Polya {
	static int p[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 };

	/**
	 * 
	 * @param m
	 *            ring size
	 * @param n
	 *            color options
	 * @return number of different rings
	 */
	static int polya(int m, int n) {
		int sum = 0;
		boolean used[];
		int cir, k;
		for (int i = 0; i < m; i++) {
			used = new boolean[m];
			cir = 0;
			for (int j = 0; j < m; j++) {
				if (!used[j]) {
					cir++;
					k = j;
					while (!used[k]) {
						used[k] = true;
						k = (i - k + m) % m;
					}
				}
			}
			sum += pow(n, cir);
		}
		return (m * N(m, n) + sum) / (2 * m);
	}

	static int N(int m, int n) {
		int sum = 0;
		for (int i = 1; i <= m; i++)
			if (m % i == 0) {
				sum += pow(n, i) * phi(m / i);
			}
		return sum / m;
	}

	static int pow(int n, int m) {
		int mul = 1;
		for (int i = 0; i < m; i++)
			mul *= n;
		return mul;
	}

	static int phi(int n) {
		int len = p.length;
		int fz = 1;
		for (int i = 0; i < len; i++) {
			if (n % p[i] == 0) {
				n /= p[i];
				fz *= p[i] - 1;
			}
		}
		return fz * n;
	}

}
